#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun  9 20:28:20 2018
@project: 天池比赛-A股主板上市公司公告信息抽取
@group: MZH_314
@author: LHQ


最小编辑距离
"""


def editdistance(seq1:str, seq2:str):
    len_seq1 = len(seq1) + 1
    len_seq2 = len(seq2) + 1
    matrix = [[0 for n in range(len_seq1)] for _ in range(len_seq2)]
    for i in range(len_seq1):
        matrix[0][i] = i
    for j in range(len_seq2):
        matrix[j][0] = j
    for i in range(1, len_seq1):
        char_i = seq1[i-1]
        for j in range(1, len_seq2):
            char_j = seq2[j-1]
            if char_i == char_j:
                cost = 0
            else:
                cost = 1
            matrix[j][i] = min(matrix[j-1][i-1] + cost,
                                matrix[j][i-1] + 1,
                                matrix[j-1][i] + 1)
    return matrix[-1][-1]



if __name__ == "__main__":
    import pprint
    s1 = "hello"
    s2 = "holle455"
    m = editdistance(s1, s2)
    pprint.pprint(m)
